package com.HUT;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    public static void main(String[] args) {
        //1.BM3验证ip地址
        public String solve (String IP) {
            if (isIPv4(IP)) {
                return "IPv4";
            }else if (isIPv6(IP)) {
                return "IPv6";
            } else {
                return "Neither";
            }
        }
        public boolean isIPv4(String IP) {
            if (IP.indexOf('.') == -1) {
                return false;
            }
            String[] ip4 = IP.split("\\.");
            if (ip4.length != 4) {
                return false;
            }
            for (int i = 0; i < ip4.length; i++) {
                if (ip4[i].length() == 0) {
                    return false;
                }
                if (ip4[i].length() < 0 || ip4[i].length() > 3 || (ip4[i].charAt(0) == '0') &&
                        (ip4[i].length() != 1)) {
                    return false;
                }
                int ret = 0;
                for (int j = 0; j < ip4[i].length(); j++) {
                    char ch = ip4[i].charAt(j);
                    if (ch < '0' || ch > '9') {
                        return false;
                    }
                    ret = ret * 10 + (int)(ch - '0');
                    if (ret < 0 || ret > 255) {
                        return false;
                    }
                }
            }
            return true;
        }
        public boolean isIPv6(String IP) {
            if (IP.indexOf(':') == -1) {
                return false;
            }
            String[] ip6 = IP.split(":",-1);
            if (ip6.length != 8) {
                return false;
            }
            for (int i = 0; i < ip6.length; i++) {
                if (ip6[i].length() == 0 || ip6[i].length() > 4 ) {
                    return false;
                }
                for (int j = 0; j < ip6[i].length(); j++) {
                    char ch1 = ip6[i].charAt(j);
                    boolean ex = (ch1 >= '0' && ch1 <= '9') || (ch1 >= 'a' && ch1 <= 'f') ||
                            (ch1 >= 'A' &&
                                    ch1 <= 'F');
                    if (!ex) {
                        return false;
                    }
                }
            }
            return true;
        }
        //2.BM3合并区间
        ArrayList<Interval> ret = new ArrayList<>();
        public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
            //判断intercals中是否存在元素
            if(intervals.size() == 0) {
                return ret;
            }
            //对intervals中的区间排序，按照区间首排序
            Collections.sort(intervals,new Comparator<Interval> () {
                public int compare(Interval o1,Interval o2) {
                    if(o1.start != o2.start) {
                        return o1.start - o2.start;
                    } else {
                        return o1.end - o2.end;
                    }
                }
            });
            //将第一个区间放入ret中
            ret.add(intervals.get(0));
            int count = 0;
            for(int i = 1;i < intervals.size();i++) {
                Interval num1 = intervals.get(i);
                Interval num2 = ret.get(count);
                //比较intervals与ret的区间，看是否有重叠
                if(num2.end < num1.start) {
                    ret.add(num1);
                    count++;
                } else {
                    //有重叠，则直接将ret中的移除
                    ret.remove(count);
                    //构建一个新的Interval的数据
                    Interval res = new Interval(num2.start,num1.end);
                    //再次判断intervals和ret的尾区间
                    if(num2.end > num1.end) {
                        res.end = num2.end;
                    }
                    ret.add(res);
                }
            }
            return ret;
        }
    }
}